package dst.graph;

import dataStructures.list.Queue;
import dataStructures.list.Stack;
import dst.graph.explorer.SearchExplorer;
import dst.graph.explorer.TreeExplorer;
import java.util.Iterator;

/**
 *
 * @author Shimu
 * @date 3-Oct-2012
 */
public class GraphFunctions {

    private static int SEARCH_ID = Integer.MIN_VALUE;

    /**
     * A TreeExplorer for resetting the searchId of all the TreeNodes
     * in this Tree.
     */
    private static class ResetExplorer<T> implements TreeExplorer<T> {

        private ResetExplorer() {
        }

        /**
         * Sets the given node's search_id to Integer.MIN_VALUE, effectively
         * reseting the search_id. Returns false.
         * 
         * @param node the node which requires search_id resetting
         * @return false
         */
        public boolean exploreCurrent(GraphSearchable<T> node) {
            node.setColor(Integer.MIN_VALUE);
            return false;
        }
    }
    
    /**
     * Increments the search id. Resets the whole tree's search id
     * using depthFirstExplore if the search id reached its maximum
     * value.
     */
    private static void incrementSearchId() {
        if (SEARCH_ID == Integer.MAX_VALUE) {
            SEARCH_ID = Integer.MIN_VALUE + 1;
            // Resets the whole tree's search_id value to Byte.MIN_VALUE
            // Need to reset the whole tree's search id
            //depthFirstExplore(new ResetExplorer<T>());
        } else {
            SEARCH_ID++;
        }
    }

    /**
     * Performs depth-first search starting from the given node. Returns the
     * GraphNode<T> with the given data if found, null otherwise.
     * 
     * <br />
     * <b>Runtime</b>: O(|V| + |E|)
     *
     * @param startNode the GraphNode to elapsedTime the depth-first search from.
     * @param searchData
     * @return the GraphNode<T> with the given data if found, null otherwise.
     */
    public static <T> GraphSearchable<T> depthFirstSearch(
            GraphSearchable<T> startNode, T searchData) {
        SearchExplorer<T> explorer = new SearchExplorer<T>(searchData);
        depthFirstExplore(startNode, explorer);

        GraphSearchable<T> returnNode = explorer.getReturnNode();
        if (returnNode != null) {
            //returnNode.returnCount++;
        }
        return returnNode;
    }
    
    public static <T> void depthFirstExplore(GraphSearchable<T> startNode,
            TreeExplorer<T> explorer) {
        startNode.setColor(SEARCH_ID);
        GraphSearchable<T> current = startNode;
        Stack<GraphSearchable<T>> stack = new Stack<GraphSearchable<T>>();

        while ((current != null) && (!explorer.exploreCurrent(current))) {
            Iterator<? extends GraphSearchable<T>> neighbours = 
                    current.getNeighbours();
            GraphSearchable<T> child;
            while (neighbours.hasNext()) {
                child = neighbours.next();
                if (child.getColor() != SEARCH_ID) {
                    child.setColor(SEARCH_ID);
                    // increment child explorer count
                    stack.push(child);
                }
            }
            current = stack.pop();
        }
        incrementSearchId();
    }

    /**
     * Searches this Tree starting at the given startNode, for the given
     * searchData and returns the GraphNode, with the given searchData if found.
     * Otherwise, returns null.
     *
     * <br />
     * <b>Runtime</b>: O(|V| + |E|)
     *
     * @param startNode 
     * @param searchData the data to be searched in the Tree
     * @return the GraphNode<T> with the given data if found, null otherwise.
     */
    public static <T> GraphSearchable<T> breadthFirstSearch(GraphNode<T> startNode,
            T searchData) {
        SearchExplorer<T> explorer = new SearchExplorer<T>(searchData);
        breadthFirstExplore(startNode, explorer);

        GraphSearchable<T> returnNode = explorer.getReturnNode();
        if (returnNode != null) {
            //returnNode.returnCount++;
        }
        return returnNode;
    }
    
    public static <T> void breadthFirstExplore(GraphSearchable<T> startNode,
            TreeExplorer<T> explorer) {
        GraphSearchable<T> current = startNode;
        startNode.setColor(SEARCH_ID);
        Queue<GraphSearchable<T>> queue = new Queue<GraphSearchable<T>>();

        while ((current != null) && !explorer.exploreCurrent(current)) {
            Iterator<? extends GraphSearchable<T>> neighbours = 
                    current.getNeighbours();
            GraphSearchable<T> child;
            while (neighbours.hasNext()) {
                child = neighbours.next();
                if (child.getColor() != SEARCH_ID) {
                    child.setColor(SEARCH_ID);
                    // increment child explorer count
                    queue.enqueue(child);
                }
            }
            current = queue.dequeue();
        }

        incrementSearchId();
    }
}
